package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-03
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。
 *
 * 现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。
 */
public class leetcode787 {
    private int[][] graph;
    private boolean[] visited;
    private int res = Integer.MAX_VALUE;
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        k = Math.min(k,n-2);

        this.graph = new int[n][n];
        for (int[] flight : flights) {
            graph[flight[0]][flight[1]] = flight[2];
        }
        this.visited = new boolean[n];
        dfs(src,dst,k+1,0);
        return res==Integer.MAX_VALUE? -1:res;
    }
    public void dfs(int src,int dst,int k,int cost){
        if (src==dst) {
            res = cost;
            return;
        }
        if (k==0) return;

        for (int i = 0; i < graph[src].length; i++) {
            // >0表示src到i有连线 两个if为剪枝
            if (graph[src][i]>0) {
                if (visited[i]) continue;

                if (cost + graph[src][i] > res) continue;

                visited[i] = true;
                dfs(i, dst, k - 1, cost + graph[src][i]);
                visited[i] = false;
            }
        }
    }
}
